package day1;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] array = {0, 1, 1, 2};
        int[] result = searchRange(array, 1);
        System.out.println();
    }

    public static int[] searchRange(int[] nums, int target) {
        //查找第一个出现的target
        int first = binarySearch(nums, target);
        //判断有没有查找到
        if (first < nums.length && nums[first] == target) {
            //如果查找到了，说明有这个值，我们再来查(target + 1)，如果有这个值，
            //那么查找的结果也是第一次出现的(target + 1)的下标，我们减去1，就是target
            //最后一次出现的下标。如果没有(target + 1)这个值，那么查找的结果就是第一个
            // 大于target的下标，我们减去1也是target最后一次出现的下标。所以这里
            // 无论有没有(target + 1)这个值，都不影响
            int last = binarySearch(nums, target + 1) - 1;
            return new int[]{first, last};
        } else {
            //没有找到这个值，直接返回{-1, -1}
            return new int[]{-1, -1};
        }
    }

    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            int midValue = nums[mid];
            if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }


}


